/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null){
            return null;
        }
        ConvertChild(pRootOfTree);

        // 4. 找到头节点
        TreeNode head  =  pRootOfTree;
        while(pRootOfTree.left != null){
            pRootOfTree = pRootOfTree.left;
            head = pRootOfTree;
        }
        return head;

    }

    //利用中序遍历思想，来实现转换链表

    public static TreeNode prev = null;

    public static void ConvertChild(TreeNode root){
        if(root == null){
            return;
        }
        //1.先左再根后右
        //走到最后一个左子树，此时root是节点4
        ConvertChild(root.left);//1
       
        // 2. 转换成链表
        root.left = prev;//把1的前驱置为null，prev初始化为null

        //第一次交换时，prev为null
        if(prev != null){
            prev.right = root;//后驱，root每次循环返回是上一个节点
        }
        prev = root;

        //3.遍历右子树
        ConvertChild(root.right);

    }
}
